1. Field of the Invention
This invention relates to improvements in optimization techniques using mixed integer programming (MIP).
2. Description of the Related Art
Optimization methods are used in a variety of applications for determining the optimal solution of a practical problem. Applications of optimization methods include, for example, worker shift planning, flow problems, packaging problems, time-table optimization, resource allocation, financial optimization problems and many others. In a typical optimization task, the problem is expressed using a set of constraints defined over variables, and an objective function defined over a subset of the variables. The optimization process seeks a solution that satisfies the constraints, while maximizing or minimizing the objective function.
Linear programming is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Mixed integer programming (MIP) is a specialization of linear programming, in which a portion of the variables are required to be integers. It is a well established method for combinatorial optimization. The problem solving process typically involves two steps: modeling and mathematical solving. In the modeling phase, a problem is trans-lated from its natural language description into an MIP language formulation of variables, linear constraints over those variables and an objective function for which an extremum is to be found. The solving phase is the process of getting a best solution to the MIP format of the problem. Several good MIP solving tools (called ‘solvers’) are available, such as CPLEX® and the COIN-OR (COmputational INfrastructure for Operations Research) open source project. However, as good as these solvers are—one often encounters problems that take considerable time to solve or fail to converge to an acceptable solution.
For example, the document An Iterative Fixing Variable Heuristic for Solving a Combined Blending and Distribution Planning Problem, Bilge Bilgen, in T. Boyanov et al. (Eds.): NMA 2006, LNCS 4310, pp. 231-238, (2007), describes a mixed integer programming (MIP) model in which a heuristic solution is used to deal with problems having large numbers of variables. This involves an iterative rounding technique in which a variable with highest fractional value is rounded to the nearest integer. While this approach conserves computational effort, the authors concede that their approach yields results that are not very close to optimality for larger problems.